#include <iostream>
#include <vector>
class sort
{
public:
    void InsertSort(std::vector<int> &v)
    {
        // 插入排序
        for (size_t i = 0; i < v.size(); ++i)
        {
            for (int j = i; j > 0; --j)
            {
                if (v[j] < v[j - 1])
                {
                    std::swap(v[j], v[j - 1]);
                }
                else
                {
                    break;
                }
            }
        }
    }
    void BubbleSort(std::vector<int> &v)
    {
        for (size_t i = 0; i < v.size(); ++i)
        {
            for (size_t j = 0; j < v.size() - i; ++j)
            {
                if (v[j + 1] < v[j])
                {
                    std::swap(v[j + 1], v[j]);
                }
            }
        }
    }
    void QuickSort(std::vector<int> &v)
    {
        _QuickSort(v, 0, v.size() - 1);
    }
    void _QuickSort(std::vector<int> &v, int begin, int end)
    {
        if (begin >= end)
        {
            return;
        }
        int left = begin;
        int right = end;

        int keyi = _MedianOfThree(v, begin, end);
        // int keyi = begin;
        while (begin < end)
        {
            while (begin < end && v[end] >= v[keyi])
            {
                --end;
            }
            while (begin < end && v[begin] <= v[keyi])
            {
                ++begin;
            }
            std::swap(v[begin], v[end]);
        }
        std::swap(v[keyi], v[end]);
        keyi = end;
        _QuickSort(v,left,keyi-1);
        _QuickSort(v,keyi+1,right);
    }

protected:
    int _MedianOfThree(std::vector<int> &v, int begin, int end)
    {
        if(end-begin < 3)
        {
            return v[begin];
        }
        int median = v.size() / 2;
        if ((v[median] > v[begin] && v[median] < v[end]) || (v[median] < v[begin] && v[median] > v[end]))
        {
            return median;
        }
        else if ((v[begin] > v[median] && v[begin] < v[end]) || v[begin] < v[median] && v[begin] > v[end])
        {
            return begin;
        }
        else if ((v[end] > v[median] && v[end] < v[begin]) || v[end] < v[median] && v[end] > v[begin])
        {
            return end;
        }
    }
};

int main()
{
    std::vector<int> v;
    for (size_t i = 0; i < 20; ++i)
    {
        v.push_back(rand() % 20);
    }
    sort s;
    s.QuickSort(v);
    for (auto &e : v)
    {
        std::cout << e << " ";
    }
    std::cout << std::endl;
    return 0;
}